package com.mccken.practice.data_structure.data_01;

import java.util.HashMap;

/**
 * LRUCache 的主方法，get 和 put 尽量避免直接操作map和cache的细节，在两种数据结构上提供了一层抽象API
 * 
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-27 14:34
 **/
public class LRUCache implements ILRUCache {
	
	private HashMap<Integer, Node_01> map;
	private DoubleList_01 cache;
	
	private int cap;
	
	public LRUCache(int capactity) {
		this.cap = capactity;
		this.map = new HashMap<Integer, Node_01>();
		this.cache = new DoubleList_01();
	}
	
	// 将某个key，提升为最近使用
	private void makeRecently(int key) {
		Node_01 x = map.get(key);
		// 从链表中删除这个节点
		cache.remove(x);
		// 重新插入到队尾
		cache.addLast(x);
	}
	
	// 添加最近使用的元素
	private void addRecently(int key, int value) {
		Node_01 x = new Node_01(key, value);
		cache.addLast(x);
		map.put(key, x);
	}
	
	
	//删除某一个key
	private void deleteKey(int key) {
		Node_01 x = map.get(key);
		// 从链表中删除
		cache.remove(x);
		// 从map中删除
		map.remove(x);
	}
	
	// 删除最久未使用的元素
	private void removeLeastRecently() {
		Node_01 deleteNode = cache.removeFirst();
		map.remove(deleteNode.key);
	}

	@Override
	public int get(int key) {
		if (!map.containsKey(key)) {
			return -1;
		}
		
		// 让这个key，成为最近使用
		makeRecently(key);
		return map.get(key).value;
	}

	@Override
	public void put(int key, int value) {
		// 如果存在key，则删除旧数据
		if (map.containsKey(key)) {
			deleteKey(key);
			addRecently(key, value);
		} else { // 如果不存在key，则判断是否超过容量
			if (cap == cache.size()) {
				// 删除最久未使用的元素
				removeLeastRecently();
			}
			// 添加为最近最少使用的元素
			addRecently(key,value);
		}
	}
	
}
